A common problem faced in optimizing a process is the selection of appropriate sets of variable parameters for controlling the process, and the development of new sets to try on the basis of results obtained. For example, a product made by a manufacturing process may have a complicated dependence on various controllable factors such as temperatures, pressures, flow rates, and the like. In order to improve or to optimize the result of such a process, the process may be performed with a number of sets of values for such controllable factors until a product of sufficient or apparent maximum quality is obtained.
A database search involves similar problems. In this type of process, optimization methods may be used to improve a prediction as to whether an item in a database may satisfy some selected criterion. An item may include a number of characteristics. A search is performed using a number of sets of test characteristics, which are varied until a sufficient number of items which match the test set satisfy the selected criterion. Those which do not match the test set should not satisfy the selected criterion.
The range of possible results of a process combined with the range of possible parameters is known as the search space of the process. A difficult problem related to optimization methods is overcoming local maxima in the search space. This problem is related to the selection and generation of trial sets of parameters for the process. For instance, most optimization methods are "hill-climbing" methods which use small variations in the process parameters of known sets of parameters to generate new trial sets for each time the process is performed. When a local maximum is reached, a less than optimal result is obtained with such small variations to the process parameters on subsequent attempts. Thus, a local maximum may appear to be the optimal result, when, in fact, other maxima may exist. In an attempt to overcome this problem, most optimization or "hill-climbing" methods avoid known or discovered local maxima. Some methods are not capable of overcoming local maxima. Others may overcome local maxima, but require extensive experimentation and trials and often take an unacceptable length of time.
One method for optimization is known as a genetic learning process. This process is so named because it involves steps for selecting and generating additional trial sets of parameters which steps are similar to those known as mutation and crossover (for generation) and "survival of the fittest" (for selection) in genetics.
The processes for set generation are illustrated graphically in FIGS. 1 and 2. FIG. 1 illustrates an example of mutation of a set. A set 31 includes six process parameters 30, 32, 34, 36, 38 and 40 for a process. A value (e.g. "A") is provided for each parameter (e.g., 30). An additional set is generated by changing (mutating) at least one of the parameters of set 31. In this example, parameters 32 and 40 have been changed. By the process of mutation, for each mutated set, one additional set is obtained.
FIG. 2 illustrates crossing (or crossover) between two sets. In this example, set 31 is crossed with another set 44 containing process parameters 46, 48, 50, 52, 54 and 56. Each set contains different values for the same process parameters. With crossover, two additional sets 58 and 60 are generated by mixing the values for the parameters of the crossed sets.
Selection of trial sets for analysis typically is based on the quality of the result of the process based on a given trial set. Trial sets whose results are of low quality typically are ignored or rejected in the selection process. In genetic processes in particular, selection of a trial set is based on the principle of "survival of the fittest" where fitness is determined by the quality of the result of the process when performed according to the trial set. Thus, those trial sets whose product is of low quality have a low fitness and typically are expressly rejected.
An example of the determination of fitness for selection will now be provided in connection with Table I. In this example, each trial set (a through e) is represented by an ordered pair of numbers. This representation will be relevant in connection with the detailed description of the present invention below. For each trial set, a quality of the result of the process was determined. Next, a value representing its fitness was determined according to a formula known as the "Standard Fitness". This formula (equation 1) sets the fitness f.sub.i of a set i based on its quality q.sub.i and the sum of all quality values q.sub.j for all j sets. ##EQU1##
TABLE I ______________________________________ (f.sub.i) Standard Trial Set Quality (q.sub.i) Fitness ______________________________________ A (1, 4) 4 0.4 B (3, 1) 3 0.3 C (1, 2) 2 0.2 D (1, 1) 1 0.1 E (7, 5) 0 0 ______________________________________
The fitness (f.sub.i) of a trial set is defined as the probability that the trial set will be selected for further analysis. That is, a trial set is selected probablistically according to the standard fitness for further analysis (i.e., generation of additional sets by mutation or crossover and performance of the process according to the additional sets).
This method of selection allows little flexibility in influencing selection of trial sets because selection is based on only one criterion and because items of quality zero are expressly rejected. Furthermore, these genetic learning processes have been of merely academic interest and have not as yet been successfully applied to solving problems of commercial interest.
Accordingly, it is an object of the present invention to provide a data processing system and method for searching for improved selection of process parameters which allows more flexibility in influencing selection of trial sets.
It is another object of the invention to apply genetic learning processes to the optimization of manufacturing processes.
It is another object of the invention to apply genetic learning processes to the improvement of product designs.
It is another object of the invention to apply genetic learning processes to database search problems.